{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Difference Between Node and Ancestor"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxAncestorDiff"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #节点与其祖先之间的最大差值"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定二叉树的根节点 <code>root</code>，找出存在于 <strong>不同</strong> 节点 <code>A</code> 和 <code>B</code> 之间的最大值 <code>V</code>，其中 <code>V = |A.val - B.val|</code>，且 <code>A</code> 是 <code>B</code> 的祖先。</p>\n",
    "\n",
    "<p>（如果 A 的任何子节点之一为 B，或者 A 的任何子节点是 B 的祖先，那么我们认为 A 是 B 的祖先）</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/11/09/tmp-tree.jpg\" style=\"width: 400px; height: 390px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [8,3,10,1,6,null,14,null,null,4,7,13]\n",
    "<strong>输出：</strong>7\n",
    "<strong>解释： </strong>\n",
    "我们有大量的节点与其祖先的差值，其中一些如下：\n",
    "|8 - 3| = 5\n",
    "|3 - 7| = 4\n",
    "|8 - 1| = 7\n",
    "|10 - 13| = 3\n",
    "在所有可能的差值中，最大值 7 由 |8 - 1| = 7 得出。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/11/09/tmp-tree-1.jpg\" style=\"width: 250px; height: 349px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [1,null,2,null,0,3]\n",
    "<strong>输出：</strong>3\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>树中的节点数在 <code>2</code> 到 <code>5000</code> 之间。</li>\n",
    "\t<li><code>0 <= Node.val <= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-difference-between-node-and-ancestor](https://leetcode.cn/problems/maximum-difference-between-node-and-ancestor/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-difference-between-node-and-ancestor](https://leetcode.cn/problems/maximum-difference-between-node-and-ancestor/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[8,3,10,1,6,null,14,null,null,4,7,13]', '[1,null,2,null,0,3]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maxAncestorDiff(self, root: TreeNode) -> int:\n",
    "        ans =0 \n",
    "        if not root:\n",
    "            return 0\n",
    "        \n",
    "        def dfs(node,max_an,min_an):\n",
    "            nonlocal ans\n",
    "            if not node:\n",
    "                return \n",
    "            \n",
    "            if abs(max_an-node.val) > ans:\n",
    "                ans = abs(max_an-node.val)\n",
    "            if abs(min_an-node.val) > ans:\n",
    "                ans = abs(min_an-node.val)\n",
    "               \n",
    "            max_an = max(max_an,node.val)\n",
    "            min_an = min(min_an,node.val)\n",
    "            dfs(node.left,max_an,min_an)\n",
    "            dfs(node.right,max_an,min_an)\n",
    "        dfs(root,root.val,root.val)\n",
    "        \n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maxAncestorDiff(self, root: TreeNode) -> int:\n",
    "        max_diff = 0\n",
    "        stack = []\n",
    "        if root is not None:\n",
    "            stack.append((root, root.val, root.val))\n",
    "        while stack:\n",
    "            node, min_val, max_val = stack.pop()\n",
    "            if node.left is not None or node.right is not None:\n",
    "                if node.left:\n",
    "                    stack.append((node.left, min(min_val, node.left.val), max(max_val, node.left.val)))\n",
    "                if node.right:\n",
    "                    stack.append((node.right, min(min_val, node.right.val), max(max_val, node.right.val)))\n",
    "            else:\n",
    "                max_diff = max(max_diff, max_val - min_val)\n",
    "        return max_diff"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maxAncestorDiff(self, root: TreeNode) -> int:\n",
    "        ans = float('-inf')\n",
    "        dp = [(root, root.val, root.val)]\n",
    "        while dp:\n",
    "            t, m, s = dp.pop()\n",
    "            if t:\n",
    "                ans = max(ans, abs(m-t.val), abs(s-t.val))\n",
    "                dp.append((t.left, max(t.val,m), min(t.val, s)))\n",
    "                dp.append((t.right, max(t.val,m), min(t.val, s)))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maxAncestorDiff(self, root: TreeNode) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "\n",
    "        res = 0\n",
    "        queue = collections.deque()\n",
    "        queue.append((root, [root.val]))\n",
    "        max_val = 0\n",
    "        while queue:\n",
    "            node, temp = queue.popleft()\n",
    "            temp_max = max(temp) - min(temp)\n",
    "            max_val = max(temp_max, max_val)\n",
    "\n",
    "            if node.left:\n",
    "                array = temp + [node.left.val]\n",
    "                queue.append((node.left, array))\n",
    "\n",
    "            if node.right:\n",
    "                array = temp + [node.right.val]\n",
    "                queue.append((node.right, array))\n",
    "\n",
    "        return max_val\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxAncestorDiff(self, root: TreeNode) -> int:\n",
    "        res=0\n",
    "        def traverse(node):\n",
    "            stack=[node]\n",
    "            remain=[]\n",
    "            while len(stack)!=0:\n",
    "                l=len(stack)\n",
    "                for i in range(l):\n",
    "                    p=stack.pop()\n",
    "                    remain.append(p.val)\n",
    "                    if p.left:\n",
    "                        stack.append(p.left)\n",
    "                    if p.right:\n",
    "                        stack.append(p.right)\n",
    "            max_num,min_num=max(remain),min(remain)\n",
    "            return max_num,min_num\n",
    "        stack=[root]\n",
    "        while len(stack)!=0:\n",
    "            l=len(stack)\n",
    "            for i in range(l):\n",
    "                p=stack.pop()\n",
    "                max_num,min_num=traverse(p)\n",
    "                res=max(res,abs(p.val-max_num),abs(p.val-min_num))\n",
    "                if p.left:\n",
    "                    stack.append(p.left)\n",
    "                if p.right:\n",
    "                    stack.append(p.right)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxAncestorDiff(self, root: TreeNode) -> int:\n",
    "        self.t=-1\n",
    "        queue=[]\n",
    "        nodequeue=[]\n",
    "        if root==None:\n",
    "            return\n",
    "        else:\n",
    "            queue.append(root)\n",
    "        while queue:\n",
    "            curNode=queue.pop(0)\n",
    "            nodequeue.append(curNode)\n",
    "            if curNode.left:\n",
    "                queue.append(curNode.left)\n",
    "            if curNode.right:\n",
    "                queue.append(curNode.right)\n",
    "        for i in nodequeue:\n",
    "            self.getsa(i)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        print(self.t)\n",
    "        return self.t\n",
    "\n",
    "    def getsa(self, root):\n",
    "        queue=[]\n",
    "        re=[]\n",
    "        if root==None:\n",
    "            return\n",
    "        else:\n",
    "            queue.append(root)\n",
    "        while queue:\n",
    "            curNode=queue.pop(0)\n",
    "            re.append(curNode.val)\n",
    "            if curNode.left:\n",
    "                queue.append(curNode.left)\n",
    "            if curNode.right:\n",
    "                queue.append(curNode.right)\n",
    "        sub=[re[0] for i in range(len(re))]\n",
    "        result= [a - b for a, b in zip(re, sub)]\n",
    "        sa=list(map(abs,result))\n",
    "        sa=max(sa)\n",
    "        if sa>self.t:\n",
    "            self.t=sa\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maxAncestorDiff(self, root: TreeNode) -> int:\n",
    "        mdict = {}\n",
    "        V = 0\n",
    "        stk = [root]\n",
    "        while stk[-1].left:\n",
    "            stk.append(stk[-1].left)\n",
    "        while len(stk) > 0:\n",
    "            top = stk[-1]\n",
    "            if top not in mdict:\n",
    "                if top.left:\n",
    "                    lmin, lmax = mdict[top.left]\n",
    "                    V = max(V, abs(top.val - lmin), abs(top.val - lmax))\n",
    "                    mdict[top] = (min(top.val, lmin), max(top.val, lmax))\n",
    "                else:\n",
    "                    mdict[top] = (top.val, top.val)\n",
    "                \n",
    "                if top.right:\n",
    "                    stk.append(top.right)\n",
    "                    while stk[-1].left:\n",
    "                        stk.append(stk[-1].left)\n",
    "            else:\n",
    "                stk.pop()\n",
    "                cur_min, cur_max = mdict[top]\n",
    "                if top.right:\n",
    "                    rmin, rmax = mdict[top.right]\n",
    "                    V = max(V, abs(top.val - rmin), abs(top.val - rmax))\n",
    "                    mdict[top] = (min(cur_min, rmin), max(cur_max, rmax))\n",
    "        return V\n",
    "\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxAncestorDiff(self, root: TreeNode) -> int:\n",
    "        ans = 0\n",
    "        queue = collections.deque()\n",
    "        queue.append([[], root])\n",
    "        while queue:\n",
    "            Len = len(queue)\n",
    "            for i in range(Len):\n",
    "                res, node = queue.popleft()\n",
    "                res.sort()\n",
    "                if res:\n",
    "                    ans = max(ans, abs(node.val - res[0]), abs(node.val - res[-1]))\n",
    "                if node.left:\n",
    "                    queue.append([res + [node.val], node.left])\n",
    "                if node.right:\n",
    "                    queue.append([res + [node.val], node.right])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxAncestorDiff(self, root: TreeNode) -> int:\n",
    "        maxdiff=0\n",
    "        stack=[root]\n",
    "        stackval=[root.val]\n",
    "        cur=root\n",
    "        while stack:\n",
    "            node=stack[-1]\n",
    "            if node.left and node.left!=cur and node.right!=cur:\n",
    "                stack.append(node.left)\n",
    "                stackval.append(node.left.val)\n",
    "            elif node.right and node.right!=cur:\n",
    "                stack.append(node.right)\n",
    "                stackval.append(node.right.val)\n",
    "            else:\n",
    "                if not node.left and not node.right:\n",
    "                    maxdiff=max(maxdiff,max(stackval)-min(stackval))\n",
    "                cur=stack.pop()\n",
    "                stackval.pop()\n",
    "        return maxdiff"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxAncestorDiff(self, root: Optional[TreeNode]) -> int:\n",
    "        \n",
    "        stack = [[root, root.val, root.val]]\n",
    "        res = 0\n",
    "        while stack:\n",
    "            node, mi, ma = stack.pop()\n",
    "            res = max(ma - mi, res)\n",
    "            if (n := node.left):\n",
    "                stack.append([n, min(n.val, mi), max(n.val, ma)])\n",
    "            if (n := node.right):\n",
    "                stack.append([n, min(n.val, mi), max(n.val, ma)])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "import copy\n",
    "\n",
    "class Solution:\n",
    "    def maxAncestorDiff(self, root: Optional[TreeNode]) -> int:\n",
    "        l = [[root, root.val, root.val]]\n",
    "        res = []\n",
    "\n",
    "        ret = 0\n",
    "\n",
    "        while l:\n",
    "            node, max_val, min_val = l.pop()\n",
    "\n",
    "            if node.left:\n",
    "                if node.left.val > max_val:\n",
    "                    max_val1 = node.left.val\n",
    "                else:\n",
    "                    max_val1 = max_val\n",
    "                \n",
    "                if node.left.val < min_val:\n",
    "                    min_val1 = node.left.val\n",
    "                else:\n",
    "                    min_val1 = min_val\n",
    "\n",
    "                l.append([node.left, max_val1, min_val1])\n",
    "\n",
    "            if node.right:\n",
    "                if node.right.val > max_val:\n",
    "                    max_val2 = node.right.val\n",
    "                else:\n",
    "                    max_val2 = max_val\n",
    "                \n",
    "                if node.right.val < min_val:\n",
    "                    min_val2 = node.right.val\n",
    "                else:\n",
    "                    min_val2 = min_val\n",
    "\n",
    "                l.append([node.right, max_val2, min_val2])\n",
    "\n",
    "            \n",
    "            if not node.left and not node.left:\n",
    "                v = max_val - min_val\n",
    "                if v > ret:\n",
    "                    ret = v\n",
    "\n",
    "        return ret\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "            \n",
    "\n",
    "        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxAncestorDiff(self, root: Optional[TreeNode]) -> int:\n",
    "        rec = []\n",
    "        res = 0\n",
    "        rec.append([root,root.val,root.val,0])\n",
    "        while(len(rec) > 0):\n",
    "            # print(rec[-1][1],rec[-1][2],rec[-1][3])\n",
    "            if rec[-1][3] == 2:\n",
    "                rec.pop()\n",
    "            elif rec[-1][3] == 1:\n",
    "                rec[-1][3]=2\n",
    "                temp = rec[-1][0].right\n",
    "                if temp !=None:\n",
    "                    minv = min(temp.val,rec[-1][1])\n",
    "                    maxv = max(temp.val,rec[-1][2])\n",
    "                    if maxv - minv > res:\n",
    "                        res = maxv - minv\n",
    "                    \n",
    "                    rec.append([temp,minv,maxv,0])\n",
    "            elif rec[-1][3] == 0:\n",
    "                rec[-1][3]=1\n",
    "                temp = rec[-1][0].left\n",
    "                if temp != None:\n",
    "                    minv = min(temp.val,rec[-1][1])\n",
    "                    maxv = max(temp.val,rec[-1][2])\n",
    "                    if maxv - minv > res:\n",
    "                        res = maxv - minv\n",
    "                    rec.append([temp,minv,maxv,0])                 \n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxAncestorDiff(self, root: Optional[TreeNode]) -> int:\n",
    "        rec = []\n",
    "        res = 0\n",
    "        rec.append([root,root.val,root.val,0])\n",
    "        while(len(rec) > 0):\n",
    "            # print(rec[-1][1],rec[-1][2],rec[-1][3])\n",
    "            if rec[-1][3] == 2:\n",
    "                rec.pop()\n",
    "            elif rec[-1][3] == 1:\n",
    "                rec[-1][3]=2\n",
    "                temp = rec[-1][0].right\n",
    "                if temp !=None:\n",
    "                    minv = min(temp.val,rec[-1][1])\n",
    "                    maxv = max(temp.val,rec[-1][2])\n",
    "                    if maxv - minv > res:\n",
    "                        res = maxv - minv\n",
    "                    \n",
    "                    rec.append([temp,minv,maxv,0])\n",
    "            elif rec[-1][3] == 0:\n",
    "                rec[-1][3]=1\n",
    "                temp = rec[-1][0].left\n",
    "                if temp != None:\n",
    "                    minv = min(temp.val,rec[-1][1])\n",
    "                    maxv = max(temp.val,rec[-1][2])\n",
    "                    if maxv - minv > res:\n",
    "                        res = maxv - minv\n",
    "                    rec.append([temp,minv,maxv,0])                 \n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxAncestorDiff(self, root: Optional[TreeNode]) -> int:\n",
    "\n",
    "        ans = 0\n",
    "\n",
    "        if not root:    # 特殊情况：当根节点为空时，直接返回空列表\n",
    "            return ans\n",
    "\n",
    "        # 节点队列：储存节点\n",
    "        queue = collections.deque([(root, root.val, root.val)])\n",
    "\n",
    "        # 当节点队列非空时，在每一步迭代中，取出队首的节点\n",
    "        while queue:\n",
    "            node, max_, min_ = queue.popleft()\n",
    "\n",
    "            # 若当前节点为叶节点，则把对应路径加入答案\n",
    "            if not node.left and not node.right:\n",
    "                ans = max(ans, max_ - min_)\n",
    "            \n",
    "            # 若当前节点不是叶节点，把它的左右子节点加入队尾\n",
    "            # O(N) string concatenation\n",
    "            else:\n",
    "                if node.left:\n",
    "                    queue.append((node.left, max(max_, node.left.val), min(min_, node.left.val)))\n",
    "                \n",
    "                if node.right:\n",
    "                    queue.append((node.right, max(max_, node.right.val), min(min_, node.right.val)))\n",
    "        \n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxAncestorDiff(self, root: Optional[TreeNode]) -> int:\n",
    "\n",
    "        diff = 0\n",
    "        q = deque([ (root, inf, -inf) ])\n",
    "        while q:\n",
    "            node, lo, hi = q.popleft()\n",
    "            if node is None: continue\n",
    "            lo = min(lo, node.val)\n",
    "            hi = max(hi, node.val)\n",
    "            diff = max(diff, abs(node.val - lo), abs(node.val - hi))\n",
    "            \n",
    "\n",
    "            q.append( (node.left, lo, hi) )\n",
    "            q.append( (node.right, lo, hi) )\n",
    "\n",
    "        return diff\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxAncestorDiff(self, root: Optional[TreeNode]) -> int:\n",
    "\n",
    "        stack = []\n",
    "        stack.append(root)\n",
    "        ans = 0\n",
    "\n",
    "        dictL = defaultdict(list)\n",
    "        dictL[root] = [root.val,root.val]\n",
    "\n",
    "        while stack:\n",
    "            n = len(stack)\n",
    "\n",
    "            for _ in range(n):\n",
    "                node = stack.pop(0)\n",
    "                \n",
    "                if node.left:\n",
    "                    \n",
    "                    ans = max(ans,max(abs(dictL[node][0] - node.left.val),  abs(dictL[node][1] - node.left.val)))\n",
    "                    stack.append(node.left)\n",
    "                    dictL[node.left] = [min(dictL[node][0],node.left.val),max(dictL[node][1],node.left.val)]\n",
    "\n",
    "                if node.right:\n",
    "\n",
    "                    ans = max(ans,max(abs(dictL[node][0] - node.right.val),  abs(dictL[node][1] - node.right.val)))\n",
    "                    stack.append(node.right)\n",
    "                    dictL[node.right] = [min(dictL[node][0],node.right.val),max(dictL[node][1],node.right.val)]\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    res = 0\n",
    "    \n",
    "    def maxAncestorDiff(self,root:TreeNode)->int:\n",
    "        if not root: return 0\n",
    "        self.dfs(root,root.val, root.val)\n",
    "        return self.res\n",
    "\n",
    "    def dfs(self,root, maxValue, minValue):\n",
    "        maxValue = max(root.val, maxValue)\n",
    "        minValue = min(root.val, minValue)\n",
    "        if root.left is None and root.right is None:\n",
    "            self.res = max(self.res, abs(maxValue - minValue))\n",
    "        if root.left:\n",
    "            self.dfs(root.left,maxValue,minValue)\n",
    "        if root.right:\n",
    "            self.dfs(root.right,maxValue,minValue)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxAncestorDiff(self, root: Optional[TreeNode]) -> int:\n",
    "        root.all_differ = [0]\n",
    "        waiting = [root]\n",
    "        value_count = [0]\n",
    "        while len(waiting) > 0:\n",
    "            new_waiting = []\n",
    "            for node_i in waiting:\n",
    "                if(node_i.left is not None):\n",
    "                    # differ_left_i = [value + node_i.val - node_i.left.val for value in node_i.all_differ] + [0]\n",
    "                    differ_left_i = [max(node_i.all_differ) + node_i.val - node_i.left.val, min(node_i.all_differ) + node_i.val - node_i.left.val, 0]\n",
    "                    value_count = value_count + differ_left_i\n",
    "                    node_i.left.all_differ = differ_left_i\n",
    "                    new_waiting.append(node_i.left)\n",
    "                    # print(\"For node {}, its all differ = {}\".format(node_i.left.val, node_i.left.all_differ))\n",
    "                if(node_i.right is not None):\n",
    "                    # differ_right_i = [value + node_i.val - node_i.right.val for value in node_i.all_differ] + [0]\n",
    "                    differ_right_i = [max(node_i.all_differ) + node_i.val - node_i.right.val, min(node_i.all_differ) + node_i.val - node_i.right.val, 0]\n",
    "                    value_count = value_count + differ_right_i\n",
    "                    node_i.right.all_differ = differ_right_i\n",
    "                    new_waiting.append(node_i.right)\n",
    "                    # print(\"For node {}, its all differ = {}\".format(node_i.right.val, node_i.right.all_differ))\n",
    "            waiting = new_waiting\n",
    "        result = max(abs(max(value_count)),abs(min(value_count)))\n",
    "        return int(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxAncestorDiff(self, root: TreeNode) -> int:\n",
    "        self.result = 0\n",
    "        self.dfs(root, float(\"-inf\"), float(\"inf\"))\n",
    "        return self.result\n",
    "    \n",
    "    def dfs(self, node:TreeNode, max_val, min_val) -> None:\n",
    "        if not node:\n",
    "            return\n",
    "        #当前路径上的最大值和最小值问题\n",
    "        max_val, min_val = max(max_val, node.val), min(min_val, node.val)\n",
    "        self.result = max(max_val - min_val, self.result)\n",
    "\n",
    "        self.dfs(node.left, max_val, min_val)\n",
    "        self.dfs(node.right, max_val, min_val)\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res = 0\n",
    "\n",
    "    def dfs(self, root: TreeNode, max_val: int, min_val: int):\n",
    "        if not root:\n",
    "            return\n",
    "\n",
    "        val1 = abs(max_val - root.val)\n",
    "        val2 = abs(min_val - root.val)\n",
    "\n",
    "        if val1 >= val2 and val1 > self.res:\n",
    "            self.res = val1\n",
    "        \n",
    "        if val2 > val1 and val2 > self.res:\n",
    "            self.res = val2\n",
    "            \n",
    "        max_val = max_val if max_val > root.val else root.val\n",
    "        min_val = min_val if min_val < root.val else root.val\n",
    "        \n",
    "        self.dfs(root.left, max_val, min_val)\n",
    "        self.dfs(root.right, max_val, min_val)\n",
    "\n",
    "    def maxAncestorDiff(self, root: TreeNode) -> int:\n",
    "        self.dfs(root, root.val, root.val)\n",
    "\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maxAncestorDiff(self, root: TreeNode) -> int:\n",
    "        return self.dfs(root)[0]\n",
    "\n",
    "    def dfs(self, root):\n",
    "        diff = 0\n",
    "        mi = root.val\n",
    "        ma = root.val\n",
    "        for node in [root.left, root.right]:\n",
    "            if not node:\n",
    "                continue\n",
    "            ld, lmi, lma = self.dfs(node)\n",
    "            diff = max(diff, ld, abs(root.val - lmi), abs(root.val - lma))\n",
    "            mi = min(lmi, mi)\n",
    "            ma = max(lma, ma) \n",
    "\n",
    "        return diff, mi, ma\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "class TreeNode:\n",
    "    def __init__(self, x):\n",
    "        self.val = x\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxAncestorDiff(self, root: TreeNode) -> int:\n",
    "\n",
    "        max_diff = -1\n",
    "\n",
    "        def search(node, path):\n",
    "            nonlocal max_diff\n",
    "\n",
    "            if not node:\n",
    "                return\n",
    "\n",
    "            path.append(node.val)\n",
    "\n",
    "            if not node.left and not node.right:\n",
    "                for i in range(1, len(path)):\n",
    "                    for j in range(i):\n",
    "                        max_diff = max(max_diff, abs(path[i] - path[j]))\n",
    "\n",
    "            search(node.left, path)\n",
    "            search(node.right, path)\n",
    "\n",
    "            path.pop()\n",
    "\n",
    "        search(root, [])\n",
    "\n",
    "        return max_diff\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def dfs(self, root, max_val, min_val):\n",
    "        if not root:\n",
    "            return 0\n",
    "        new_max = max(root.val, max_val)\n",
    "        new_min = min(root.val, min_val)\n",
    "        left_max = self.dfs(root.left, new_max, new_min)\n",
    "        right_max = self.dfs(root.right, new_max, new_min)\n",
    "\n",
    "        return max(abs(root.val - max_val), abs(root.val - min_val), left_max, right_max)\n",
    "\n",
    "    def maxAncestorDiff(self, root: TreeNode) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "\n",
    "        return self.dfs(root, root.val, root.val)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\r\n",
    "# class TreeNode:\r\n",
    "#     def __init__(self, val=0, left=None, right=None):\r\n",
    "#         self.val = val\r\n",
    "#         self.left = left\r\n",
    "#         self.right = right\r\n",
    "class Solution:\r\n",
    "    _res = 0\r\n",
    "\r\n",
    "    def _minmax(self, root):\r\n",
    "        if root == None:\r\n",
    "            return None\r\n",
    "        l = self._minmax(root.left)\r\n",
    "        r = self._minmax(root.right)\r\n",
    "        if l == None and r == None:\r\n",
    "            return (root.val, root.val)\r\n",
    "        a = []\r\n",
    "        if l == None or r == None:\r\n",
    "            a = r if l == None else l\r\n",
    "        else:\r\n",
    "            a = (min(l[0], r[0]), max(l[1], r[1]))\r\n",
    "        if root.val >= a[1]:\r\n",
    "            self._res = max(self._res, root.val - a[0])\r\n",
    "            return (a[0], root.val)\r\n",
    "        if root.val <= a[0]:\r\n",
    "            self._res = max(self._res, a[1] - root.val)\r\n",
    "            return (root.val, a[1])\r\n",
    "        self._res = max(self._res, root.val - a[0], a[1] - root.val)\r\n",
    "        return a\r\n",
    "\r\n",
    "    def maxAncestorDiff(self, root: Optional[TreeNode]) -> int:\r\n",
    "        self._res = 0\r\n",
    "        self._minmax(root)\r\n",
    "        return self._res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "def dfs(root,max_res):\n",
    "    # print (root.val)\n",
    "    min_val = root.val\n",
    "    max_val = root.val\n",
    "    if root.left:\n",
    "        child_min,child_max = dfs(root.left,max_res)\n",
    "        min_val = min(min_val,child_min)\n",
    "        max_val = max(max_val,child_max)\n",
    "    if root.right:\n",
    "        child_min,child_max = dfs(root.right,max_res)\n",
    "        min_val = min(min_val,child_min)\n",
    "        max_val = max(max_val,child_max)\n",
    "    diff = max(root.val - min_val,max_val - root.val)\n",
    "    print (root.val,diff,max_val,min_val)\n",
    "    if diff > max_res[0]:\n",
    "        max_res[0] = diff\n",
    "    # diff_list.append(diff)\n",
    "    return min_val,max_val\n",
    "\n",
    "class Solution:\n",
    "    def maxAncestorDiff(self, root: TreeNode) -> int:\n",
    "        # diff_list = [] \n",
    "        max_res = [-99999999999]\n",
    "        dfs(root,max_res)\n",
    "        # print (diff_list)\n",
    "        return max_res[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    \n",
    "    def maxAncestorDiff(self, root: TreeNode) -> int:\n",
    "        result = 0\n",
    "        def helper(node, max_val, min_val):\n",
    "            if not node:\n",
    "                nonlocal result\n",
    "                result = max(max_val - min_val, result)\n",
    "                return\n",
    "            max_val, min_val = max(max_val, node.val), min(min_val, node.val)\n",
    "            helper(node.left, max_val, min_val)\n",
    "            helper(node.right, max_val, min_val)  \n",
    "        helper(root, float('-inf'), float('inf'))\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxAncestorDiff(self, root: Optional[TreeNode]) -> int:\n",
    "        res = []\n",
    "        def dfs(node, temp):\n",
    "            if node is None:return\n",
    "            temp.append(node.val)\n",
    "            if node.left is None and node.right is None:\n",
    "                res.append(temp.copy())\n",
    "            dfs(node.left, temp)\n",
    "            dfs(node.right, temp)\n",
    "            temp.pop()\n",
    "        dfs(root, [])\n",
    "        mx = 0\n",
    "        for nums in res:\n",
    "            for i in range(len(nums)):\n",
    "                for j in range(i + 1, len(nums)):\n",
    "                    mx = max(mx, abs(nums[j] - nums[i]))\n",
    "        return mx\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxAncestorDiff(self, root: Optional[TreeNode]) -> int:\n",
    "        res = 0\n",
    "        def dfs(node, mx, mi):\n",
    "            if node is None:return\n",
    "\n",
    "            nonlocal res\n",
    "            res = max(res, node.val - mi, mx - node.val)\n",
    "            mx = max(mx, node.val)\n",
    "            mi = min(mi, node.val)\n",
    "            dfs(node.left, mx, mi)\n",
    "            dfs(node.right, mx, mi)\n",
    "        dfs(root, root.val, root.val)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxAncestorDiff(self, root: Optional[TreeNode]) -> int:\n",
    "        ans = []\n",
    "        def dfs (root,fathers:list):\n",
    "            if root is None :\n",
    "                return \n",
    "            value = 0\n",
    "            for father in fathers:\n",
    "                value = max(abs(root.val-father),value)\n",
    "            fathers.append(root.val)\n",
    "            ans.append(value)\n",
    "            dfs(root.left,fathers)\n",
    "            dfs(root.right,fathers)\n",
    "            fathers.pop()\n",
    "        dfs(root,[])\n",
    "        return max(ans)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxAncestorDiff(self, root: Optional[TreeNode]) -> int:\n",
    "        ans=0\n",
    "        def dfs(root):\n",
    "            if root is None:\n",
    "                return -inf,inf\n",
    "            ma=mi=root.val\n",
    "            l_ma,l_mi=dfs(root.left)\n",
    "            r_ma,r_mi=dfs(root.right)\n",
    "            ma=max(ma,l_ma,r_ma)\n",
    "            mi=min(mi,l_mi,r_mi)\n",
    "            nonlocal ans\n",
    "            ans=max(ans,abs(ma-root.val),abs(mi-root.val))\n",
    "            return ma,mi\n",
    "        dfs(root)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxAncestorDiff(self, root: Optional[TreeNode]) -> int:\n",
    "# 递归方式找到所有路径，然后把路径上的最大和最小找出来，维护一个ans max\n",
    "        ans = 0\n",
    "\n",
    "        def find(root,da,xiao):\n",
    "            nonlocal ans\n",
    "            if not root:\n",
    "                ans = max(ans,da - xiao)\n",
    "                return\n",
    "            da = max(da,root.val)\n",
    "            xiao = min(xiao,root.val)\n",
    "            find(root.left,da,xiao)\n",
    "            find(root.right,da,xiao)\n",
    "        find(root,0,inf)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxAncestorDiff(self, root: Optional[TreeNode]) -> int:\n",
    "        def traverse(node, min_val, max_val):\n",
    "            if node:\n",
    "                min_val = min(min_val, node.val)\n",
    "                max_val = max(max_val, node.val)\n",
    "                if not node.left and not node.right:\n",
    "                    return max_val - min_val\n",
    "                return max(traverse(node.left, min_val, max_val), traverse(node.right, min_val, max_val))\n",
    "            return 0\n",
    "        return traverse(root, root.val, root.val)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxAncestorDiff(self, root: Optional[TreeNode]) -> int:\n",
    "        self.val = 0\n",
    "        \n",
    "        def travel(root):\n",
    "            if not root:\n",
    "                return None, None\n",
    "            l_max, l_min = travel(root.left)\n",
    "            r_max, r_min = travel(root.right)\n",
    "            if l_max is None:\n",
    "                if r_max is None:\n",
    "                    return root.val, root.val\n",
    "                else:\n",
    "                    if max(abs(root.val - r_max), abs(root.val - r_min)) > self.val:\n",
    "                        self.val = max(abs(root.val - r_max), abs(root.val - r_min))\n",
    "                    return max(root.val, r_max), min(root.val, r_min)\n",
    "            elif r_max is None:\n",
    "                if max(abs(root.val - l_max), abs(root.val - l_min)) > self.val:\n",
    "                    self.val = max(abs(root.val - l_max), abs(root.val - l_min))\n",
    "                return max(root.val, l_max), min(root.val, l_min)\n",
    "            else:\n",
    "                val_min = min(l_min, r_min)\n",
    "                val_max = max(l_max, r_max)\n",
    "                if max(abs(root.val - val_max), abs(root.val - val_min)) > self.val:\n",
    "                    self.val = max(abs(root.val - val_max), abs(root.val - val_min))\n",
    "                return max(root.val, val_max), min(root.val, val_min)\n",
    "        travel(root)\n",
    "        return self.val"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
